package listbyorder.access401_500.test401;

import java.util.ArrayList;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/8/21 20:33
 */
public class Solution1 {


    List<String> res = new ArrayList<>();
    int[] s = {1, 2, 3, 4};
    int[] m = {32, 16, 8, 4, 2, 1};

    public List<String> readBinaryWatch(int num) {
        if(num < 0 || num > 10) return res;

        if(num == 0) {
            res.add("0:00");
            return res;
        }

        for(int i = 0; i <= num; i++) {
            int l = i;
            int r = num - i;
            if(l > 4 || r > 6) continue;
            List<String> ls = getP(s, l, 0);
            List<String> rs = getP(m, r, 1);
            for(String s1 : ls) {
                for(String s2 : rs) {
                    res.add(s1 + ":" + s2);
                }
            }
        }

        return res;
    }

    public List<String> getP(int[] arr, int l, int f) {
        List<String> res = new ArrayList<>();
        if (l == 0) {
            res.add(f == 0 ? "0" : "00");
        } else {
            dfs(res, arr, l, 0, 0, f);
        }
        return res;
    }

    private void dfs(List<String> res, int[] arr, int l, int c, int sum, int f) {
        if (c == arr.length || sum > 12) return;
        if (l == 0) {
            String s = f == 0 ? (sum + "") : (sum < 10 ? "0" + sum : sum + "");
            res.add(s);
            return;
        }
        for (int i = c; i < arr.length; i++) {
            sum += arr[i];
            dfs(res, arr, l - 1, i + 1, sum, f);
            sum -= arr[i];
        }
    }

}
